package argo.hot100.tree;

import java.util.HashMap;
import java.util.Map;

public class PathSum {

    public int pathSum(TreeNode root, int targetSum) {
        int res = 0;

        Map<Long, Integer> prefix = new HashMap<>();
        prefix.put(0L, 1);
        res += path(root, prefix, 0L, targetSum);

        return res;
    }

    public int path(TreeNode root, Map<Long, Integer> prefix, Long curr, int targetSum) {
        if (root == null) {
            return 0;
        }
        int res = 0;
        curr += root.val;

        res = prefix.getOrDefault(curr - targetSum, 0);
        prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);

        res += path(root.left, prefix, curr, targetSum);
        res += path(root.right, prefix, curr, targetSum);

        /// 回溯：当前节点处理完毕后，从哈希表中移除当前前缀和
        //  避免影响其他分支的计算（保证哈希表状态仅对当前路径有效）
        prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);
        return res;
    }
}
